package com.learn.algorithm.dynamic.programming;

public class LeetCode72 {
    public static int minDistance(String word1, String word2) {
        return editDistance1(word1, word2, 1, 1, 1);
    }

    // a 插入代价
    // b 删除代价
    // c 替换代价
    public static int editDistance1(String str1, String str2, int a, int b, int c) {
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();
        int n = str1.length();
        int m = str2.length();
        int[][] dp = new int[n + 1][m + 1];
        // 长度为i的str1变为长度为0的str2 做i次删除
        for (int i = 1; i <= n; i++) {
            dp[i][0] = i * b;
        }
        // 从长度为0的str1变为长度为j的str2
        for (int j = 1; j <= m; j++) {
            dp[0][j] = j * a;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int p1 = Integer.MAX_VALUE;
                if (s1[i - 1] == s2[j - 1]) {
                    p1 = dp[i - 1][j - 1];
                }
                int p2 = Integer.MAX_VALUE;
                if (s1[i - 1] != s2[j - 1]) {
                    p2 = dp[i - 1][j - 1] + c;
                }
                int p3 = dp[i][j - 1] + a;
                int p4 = dp[i - 1][j] + b;
                dp[i][j] = Math.min(Math.min(p1, p2), Math.min(p3, p4));
            }
        }
        return dp[n][m];
    }

//    public static int editDistance1(String str1, String str2, int a, int b, int c) {
//
//    }

    //  dp[i][j] : str1的前i个字符变为str2前j个字符的最小花费
    //  s[i-1] 参与变换过程
    //     a. s[i-1] 变为 t[j-1]
    //        a. s[i-1] == t[j-1] 代价 0 + dp[i-1][j-1]
    //        b. s[i-1] != t[j-1] 代价 替换 + dp[i-1][j-1]
    //     b. s[i-1] 变为 t[j-2] 再通过插入最后t[j-1]的方式变换
    //        代价 插入 + dp[i][j-1]
    //  s[i-1] 不参与变换过程
    //        代价 删除 + dp[i-1][j]
}
